import java.util.Deque;
import java.util.LinkedList;
import java.util.Stack;

public class Solution {
    public boolean IsPopOrder(int [] pushA,int [] popA) {
        Stack<Integer> stack = new Stack<>();
        int j = 0;
        for(int i = 0; i < popA.length; i++){
            if(!stack.empty() && stack.peek() == popA[i]){
                stack.pop();
            }else{
                int flag = 0;
                for(; j < pushA.length; j++){
                    stack.push(pushA[j]);
                    if(stack.peek() == popA[i]){
                        stack.pop();
                        flag = 1;
                        j++;
                        break;
                    }
                }
                if(flag == 0){
                    return false;
                }
            }
        }
        return true;
    }
}

/***
 * 用队列实现栈
 */

class MyStack {
    private Deque<Integer> push;
    private Deque<Integer> pop;

    public MyStack() {
        push = new LinkedList<>();
        pop = new LinkedList<>();
    }

    public void push(int x) {
        push.offer(x);
        while(!pop.isEmpty()){
            push.offer(pop.poll());
        }
        Deque<Integer> tmp = push;
        push = pop;
        pop = tmp;
    }

    public int pop() {
        return pop.poll();
    }

    public int top() {
        return pop.peek();
    }

    public boolean empty() {
        return pop.isEmpty();
    }
}

/**
 * 用栈实现队列
 */

class MyQueue {
    private Stack<Integer> s1;
    private Stack<Integer> s2;


    public MyQueue() {
        s1 = new Stack<>();
        s2 = new Stack<>();
    }

    public void push(int x) {
        s1.push(x);
    }


    public int pop() {
        if(s2.empty()) {
            while (!s1.empty()) {
                s2.push(s1.pop());
            }
        }

        return s2.pop();

    }

    public int peek() {
        if(s2.empty()) {
            while (!s1.empty()) {
                s2.push(s1.pop());
            }
        }
        return s2.peek();
    }

    public boolean empty() {
        return s1.empty() && s2.empty();
    }
}

